#include <bits/stdc++.h>
// 递归
int gcd(int a, int b) {
  if (b == 0) {
    return a;
  }
  return gcd(b, a % b);
}
// 迭代
int gcd2(int a, int b) {
  while (b != 0) {
    int r = b;
    b = a % b;
    a = r;
  }
  return a;
}
int main() {
  int T, N, M;
  scanf("%d", &T);
  while (T--) {
    int count = 0;
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; i++) {
      if (gcd2(i, N) >= M) {
        count++;
      }
    }
    printf("%d\n", count);
  }
  return 0;
}